引入

前面我们说完了顺序存储结构的线性表的查找、插入和删除等操作，我们分析之后发现，顺训存储结构的线性表最大的缺点就是插入和删除的时候需要移动大量元素，太费时间了，我们能不能针对这个缺陷提出新的结构呢？

思考

我们现在的问题是

插入和删除的时候，要移动大量元素

原因就在于，相邻的两个元素的存储位置也具有邻居关系，也就是说它们在内存中的位置是紧密相联的。所以我们就没有办法从紧密相联的关系中插入和删除元素，并依旧保持它们紧密相联的关系了。所以指针刚好可以派上用场，每个元素多留一个位置存储下一个元素的位置指针，这样第一个元素找到第二个，第二个找到第三个….以此类推即可。

链式存储结构

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以存在内存中未被占用的任意位置。
比起顺序存储结构每个数据元素只需要存储一个位置就可以了。但是现在链式存储结构中，除了要存储数据元素信息外，还要存储它的后继元素的存储地址。

数据域和指针域

现在，每个数据元素存储着两块内容：

数据域：存储的是数据元素的信息。
指针域：存储的是直接后继位置的信息，我们把这些信息称为指针或链。
数据映像/结点：我们称由上面这两部分信息组成的数据元素位称为存储映像，也称为结点（Node）。

定义

单链表：我们把由 n 个结点链接成的一个链表，即为线性表的链式存储结构。因为每个结点都只包含一个指针域，所以叫做单链表。
头尾：对于线性表来说呢，总需要一个头和尾，我们把链表中的第一个结点称为头指针，最后一个结点指针为空（NULL）。

头结点和头指针

头指针

头指针是指向链表第一个结点的指针
链表如果有头结点，那就是指向头结点的指针
头指针具有标识作用，因为找到头指针就找到了整个链表，所以常用头指针冠以链表的名字，也就是指针变量明。
无论链表是否为空，头指针不为空，否则就没有这个链表了
头指针是链表的必要元素。

头结点

头结点是为了操作的统一和方便设立的
放在第一个元素结点之前，数据域一般无意义，指针域指向第一个数据元素。
有了头结点，对在第一个元素结点前插入结点和删除第一个结点的操作就跟其它结点的这些操作统一了。
头结点不一定是链表的必须要素。

空链表

空链表

头指针指向头结点
头结点指向 NULL

代码实现

还记得怎么在 C 语言中创建动态单链表嘛？

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof (struct Student)
struct Student{
    int num;
    char name[20];
    float score;
    struct Student *next;
};
int n;
struct Student *create(void){
    struct Student *a , *b , *head;
    a=b=(struct Student *)malloc(LEN);
    printf("请输入学生的信息:\n");
    scanf("%d %s %f", &a->num , a->name , &a->score);
    b=a;
    while(a->num!=0){
        n=n+1;
        if(n==1){
            head=a;
        }else{
            b->next=a;
            b=a;
        }
        a=(struct Student *)malloc(LEN);
        scanf("%d %s %f",&(*a).num , a->name , &a->score);
    }
    b->next=NULL;
    return head;
}

void print(struct Student *p){
    while(p!=NULL){
        printf("第%d号%s的成绩是%3.1f\n",p->num,p->name,p->score);
        p=p->next;
    }
}

int main(){
    struct Student *p_head;
    p_head=create();
    print(p_head);
    return 0;
}

学习了数据结构之后，我们再看看封装一个单链表

struct Student{
ElemType data;  //这就是数据域
struct Student *Next;  //这就是指针域
} Node;
typedef struct Student * LinkList;

所以

p -> data 就是指向数据域
p - > next 就是这样指针域
如果p->data=ai那么p->next->data=ai+1
封装单链表必须存在数据域和指针域

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。